1. Filed of the Invention
This invention relates generally to the field of computer graphics. More particularly, this invention relates to a method and apparatus for color-compression for raster image quantization using an approximation of human visual perception as a component of the compression process.
2. Background of the Invention
There are many published color-compression (or data clustering) algorithms, each having a common approach. (For purposes of this document the terms "color-compression" or simply "compression" and like terms are intended to mean any process for reducing the number of colors in an image. Complete preservation of the original uncompressed image's information content is not required, but retention of high image quality is desired.) First a quantitative error metric is defined, then an algorithm is developed in attempt to mathematically minimize the error metric. Each of the known algorithms use the same metric, namely the mean-squared summation of the Euclidean distance of the source color coordinates from the quantized color coordinates for each pel. Mathematically:
Let c[i,j] be the 24-bit color of the pel at the (i,j) coordinate whose color components are (r,g,b) out of a set of n colors.
Let q(c[i,j]) represent the quantization function resulting in the presentation color whose components are (r',g',b') out of a set of k colors.
Let d(c,c') represent the quantitative difference between the two colors c and c'.
The quantization error metric D can then be calculated as: ##EQU1##
The difference function d(c,c'), in the published algorithms, is calculated as the Euclidean distance squared between the respective components of the two colors: EQU d(c,c')=(r-r').sup.2 +(g-g').sup.2 +(b-b').sup.2
To achieve good quality images using a limited number of presentation colors (the set of colors used in the color-compressed image) selected from a larger palate of colors, the quantization process should select the set of k presentation colors that result in the lowest possible value of the error metric D. The differences between the various existing algorithms is primarily in the method of selecting the presentation color set.
The literature shows several methods for selecting the presentation color set. For example, S. J. Wan, P. Prusinkiewicz, and S. K. M. Wong, "Variance-Based Color Image Quantization for Frame Buffer Display", Color Research and Application, Vol. 15, No. 1, February 1990, pp. 52-58; S. J. Wan, S. K. M. Wong, and P. Prusinkiewicz, "An Algorithm for Multidimensional Data Clustering", ACM Transactions on Mathematical Software, Vol. 14, No. 2, June 1988, pp. 153-162; Paul Heckbert, "Color Image Quantization for Frame Buffer Display", Computer Graphics, Vol. 16, No. 3, July 1982, pp. 297-307; Ronald S. Gentile, Eric Walowit, and Jan P. Allebach, "Quantization and Multilevel Halftoning of Color Images for Near-Original Image Quality", Journal of the Optical Society of America A--Optics and Image Science, Vol. 7, No. 6, June 1990, pp. 1019-1026; G. W. Braudaway, "Procedure for Optimum Choice of a Small Number of Colors from a Large Color Palette for Color Imaging", presented at Electronic Imaging '87, San Francisco, Calif., 1987 (Also published in IBM Technical Disclosure Bulletin, Vol. 29, No. 3, August 1986, pp. 1329-1334); and Ronald S. Gentile, Jan P. Allebach, and Eric Walowit, "Quantization of Color Images Based on Uniform Color Spaces," J. Imag Tech 16, 11-21 (1990) describe various techniques for color-compression. Each of these references is hereby incorporated by reference.
These references describe several algorithms for accomplishing this task. Among them, Heckbert describes a Popularity Algorithm and a Median-Cut Algorithm (k-d Tree). Wan, et al. describe a Mean-Split Algorithm, a K-Means Iterative Algorithm and a Variance-Based Algorithm. Braudaway presents his own algorithm for this purpose.
Each of these algorithms, in their own way, have the common goal of minimizing the error metric D as defined above. But, this is an effective quantization approach only if the metric used accurately reflects the perceived quality of the image.- However, the accepted metric has two distinct, widely known shortcomings. First, the color space on which the metric is based is non-uniform and non-linear. This means that the error metric has different meanings depending on what part of the color spectrum in which the source and destination pixel colors reside. Second, The influence of spacial proximity on the perceived colors is not accounted for in the metric.
For these reasons, sometimes a change in the quantization which reduces the error metric will generate an image which exhibits degradation of image quality when displayed on a CRT monitor. S. J. Wan et al. provides experimental evidence of a case where a mathematical improvement in the error metric resulted in perceivable degradation in the displayed image.
Two major issues are raised commonly but left unresolved among the published approaches: the desirability of a uniform color space and the desirability of incorporating human perception in the quantization process. Also, most published algorithms do not attempt to approximate a uniform color space. Gentile et al. experimented with L*u*v color space, but experienced difficulty in the conversion in an RGB environment due to device dependencies and system constraints, and noted that the resulting L*u*v coordinates were not actually uniform. In this case, using the L*u*v color space failed to produce superior quality quantizations of the image files.
Another problem with the existing algorithms is that no attempt is made to allocate some small portion of the CLUT (Color Look-Up Table) for periphery colors with low histogram counts. Such colors are often visually important in spite of low histogram counts. For example, an image may have a flower pot containing daisies with white pedals and yellow centers. If those yellow centers comprise the only yellow in that image, the existing algorithms may view the yellow as unimportant because of such a small occurrence in the image color histogram, and therefore gives little contribution to the error metric. However, from the perceptual perspective, it is important that the color appears yellow as opposed to red or green.
Sometimes a color with a low histogram count is actually more important to include in the presentation colors than a color with a higher histogram count. The key point is whether another color already has been selected in the presentation colors that is "sufficiently, close" to adequately represent the color in question, regardless of that cells histogram count, and regardless of that color's contribution to a quantitative error metric.
In all of the published algorithms, once the presentation colors have been selected, the source image is read pixel-by-pixel, and for each input pixel, the Euclidean distance function (used in the error metric) is used to determine the presentation color which has the minimum distance from the source color.
The problem with this quantization method is similar to the problem with the error metric, which is that the distance function is non-uniform and non-linear. The best mathematical presentation color may not be the best perceived color to select. This is a second order perceptual error introduced into the quantization technique. Firstly, the set of presentation colors contains errors in selection due to the inaccuracies and non-uniformity of the metric on which the selection is based. Secondly, once the presentation color set is selected, sometimes the quantization function may produce errors in selecting the nearest perceived presentation color, since the distance function used is non-uniform and non-linear. This compounding of errors substantially degrades the resulting image quality.
The present invention provides an improvement in perceived image quality of a color compressed image by addressing the human perception issues in the compression process, the effects of the display and the other problems described above.